Many signal processing and compression algorithms in wide use perform a Fourier transform to translate an input signal into the frequency domain. For example, Fourier-based image and video compression schemes are among the most common and successful available in the industry today. Formats such as JPEG and MPEG (which are based on a discrete cosine transform that is similar to a Fourier transform) are especially prevalent and can be found in most commercial devices requiring video or image compression. Compression based on Fourier transforms facilitates use of robust algorithms and provides tunable performance with very good compression ratios that ultimately reduce memory storage and transmission requirements while maintaining high-quality signal reconstruction.
Fourier-based compression is a ‘lossy’ technique that achieves compression by selectively removing components from the image (or other signal) and only storing the most critical information. Typically, a Fourier transform is performed on a waveform representing a portion of an image or other signal, to derive a set of Fourier coefficients from which the waveform can be reconstructed. Compression is achieved by removing “unimportant” coefficients that do not play a significant role during reconstruction. The image quality and compression ratio can be traded off by varying the number of coefficients stored and used in this process, and the precision at which each coefficient is stored.
In addition to their use in compression, Fourier transforms are employed in many other signal-processing applications, including pattern recognition, spectrum analysis, filtering, image processing, and others. The ability to efficiently perform a Fourier transform is an operation that is important in numerous devices, including sensors, voice recognition devices, digital music players and recorders, digital cameras and video systems, and many other multi-media devices.
Traditionally, a computer processor or digital signal processor (DSP) chip, performs a “Fast Fourier Transform” (FFT) to convert spatially based or time-based information into wavespace (i.e., the frequency domain). For many applications, the FFT must be performed repeatedly and may become computationally costly. For example, for full color 640×480 video at 30 frames per second, 432,000 64-pixel image sub-blocks must be processed per second. Performing a 64-point FFT on each of these sub-blocks using the advanced Radix-2 algorithm requires 384 complex adds and 192 complex multiplies per sub-block, resulting in significant processing requirements.
While this is within the realm of processor technology, a chip capable of performing these functions draws a significant amount of power. Additionally, because these calculations are typically performed on a digital processor, it is often necessary to convert an analog signal into digital form prior to applying the calculations. The analog-to-digital conversion process may also draw a significant amount of power. While the power drain due to analog-to-digital conversion and calculation of a Fourier transform is relatively insignificant from the perspective of a desktop computer, embedded applications often require extremely small size and very lower power. The power demands of a high-performance processor or DSP that performs Fourier transforms may make their use impractical in many battery-operated embedded devices.